interface TreeHelperConfig {
	id: string;
	children: string;
	pid: string;
}

// 默认配置
const DEFAULT_CONFIG: TreeHelperConfig = {
	id: "id",
	children: "children",
	pid: "pid"
};

// 获取配置 Object.assign 从一个或多个源对象复制到目标对象
const getConfig = (config: Partial<TreeHelperConfig>) => Object.assign({}, DEFAULT_CONFIG, config);

// tree from list
// 列表中的树
export function listToTree<T = any>(list: any[], config: Partial<TreeHelperConfig> = {}): T[] {
	const conf = getConfig(config) as TreeHelperConfig;
	const nodeMap = new Map();
	const result: T[] = [];
	const { id, children, pid } = conf;

	for (const node of list) {
		node[children] = node[children] || [];
		nodeMap.set(node[id], node);
	}
	for (const node of list) {
		const parent = nodeMap.get(node[pid]);
		(parent ? parent[children] : result).push(node);
	}
	return result;
}

export function treeToList<T = any>(tree: any, config: Partial<TreeHelperConfig> = {}): T {
	config = getConfig(config);
	const { children } = config;
	const result: any = [...tree];
	for (let i = 0; i < result.length; i++) {
		if (!result[i][children!]) continue;
		result.splice(i + 1, 0, ...result[i][children!]);
	}
	return result;
}

export function findNode<T = any>(tree: any, func: Fn, config: Partial<TreeHelperConfig> = {}): T | null {
	config = getConfig(config);
	const { children } = config;
	const list = [...tree];
	for (const node of list) {
		if (func(node)) return node;
		node[children!] && list.push(...node[children!]);
	}
	return null;
}

export function findNodeAll<T = any>(tree: any, func: Fn, config: Partial<TreeHelperConfig> = {}): T[] {
	config = getConfig(config);
	const { children } = config;
	const list = [...tree];
	const result: T[] = [];
	for (const node of list) {
		func(node) && result.push(node);
		node[children!] && list.push(...node[children!]);
	}
	return result;
}

export function findPath<T = any>(tree: any, func: Fn, config: Partial<TreeHelperConfig> = {}): T | T[] | null {
	config = getConfig(config);
	const path: T[] = [];
	const list = [...tree];
	const visitedSet = new Set();
	const { children } = config;
	while (list.length) {
		const node = list[0];
		if (visitedSet.has(node)) {
			path.pop();
			list.shift();
		} else {
			visitedSet.add(node);
			node[children!] && list.unshift(...node[children!]);
			path.push(node);
			if (func(node)) return path;
		}
	}
	return null;
}

export function findPathAll(tree: any, func: Fn, config: Partial<TreeHelperConfig> = {}) {
	config = getConfig(config);
	const path: any[] = [];
	const list = [...tree];
	const result: any[] = [];
	const visitedSet = new Set();
	const { children } = config;
	while (list.length) {
		const node = list[0];
		if (visitedSet.has(node)) {
			path.pop();
			list.shift();
		} else {
			visitedSet.add(node);
			node[children!] && list.unshift(...node[children!]);
			path.push(node);
			func(node) && result.push([...path]);
		}
	}
	return result;
}

export function filter<T = any>(
	tree: T[],
	func: (n: T) => boolean,
	// Partial 将 T 中的所有属性设为可选
	config: Partial<TreeHelperConfig> = {}
): T[] {
	// 获取配置
	config = getConfig(config);
	const children = config.children as string;

	function listFilter(list: T[]) {
		return list
			.map((node: any) => ({ ...node }))
			.filter(node => {
				// 递归调用 对含有children项  进行再次调用自身函数 listFilter
				node[children] = node[children] && listFilter(node[children]);
				// 执行传入的回调 func 进行过滤
				return func(node) || (node[children] && node[children].length);
			});
	}

	return listFilter(tree);
}

export function forEach<T = any>(tree: T[], func: (n: T) => any, config: Partial<TreeHelperConfig> = {}): void {
	config = getConfig(config);
	const list: any[] = [...tree];
	const { children } = config;
	for (let i = 0; i < list.length; i++) {
		// func 返回true就终止遍历，避免大量节点场景下无意义循环，引起浏览器卡顿
		if (func(list[i])) return;

		children && list[i][children] && list.splice(i + 1, 0, ...list[i][children]);
	}
}

/**
 * @description: Extract tree specified structure
 * @description: 提取树指定结构
 */
export function treeMap<T = any>(treeData: T[], opt: { children?: string; conversion: Fn }): T[] {
	return treeData.map(item => treeMapEach(item, opt));
}

/**
 * @description: Extract tree specified structure
 * @description: 提取树指定结构
 */
export function treeMapEach(data: any, { children = "children", conversion }: { children?: string; conversion: Fn }) {
	const haveChildren = Array.isArray(data[children]) && data[children].length > 0;
	const conversionData = conversion(data) || {};
	if (haveChildren) {
		return {
			...conversionData,
			[children]: data[children].map((i: number) =>
				treeMapEach(i, {
					children,
					conversion
				})
			)
		};
	} else {
		return {
			...conversionData
		};
	}
}

/**
 * 递归遍历树结构
 * @param treeDatas 树
 * @param callBack 回调
 * @param parentNode 父节点
 */
export function eachTree(treeDatas: any[], callBack: Fn, parentNode = {}) {
	treeDatas.forEach(element => {
		const newNode = callBack(element, parentNode) || element;
		if (element.children) eachTree(element.children, callBack, newNode);
	});
}
